package com.csdemos.algs.graphs;

public class Driver {
	
	public static void main(String[] args) {
		Graph graph1 = new AdjacencyListGraph(8, true);
		Graph graph2 = new AdjacencyMatrixGraph(8);
		Graph graph3 = new AdjacencyListGraph(10, true);
		Graph graph4 = new AdjacencyMatrixGraph(10);
		Graph graph5 = new AdjacencyListGraph(9, false);
		
		fill(graph1);
		fill(graph2);
		fill2(graph3);
		fill2(graph4);
		fill3(graph5);
		
		System.out.println("Adjacency list:");
		System.out.println(DFS.Topological_Sort(graph1));
		System.out.println(DFS.Strongly_Connected_Components(graph1));
		System.out.println(DFS.Strongly_Connected_Components(graph3));
		
		System.out.println("Matrix list:");
		System.out.println(DFS.Topological_Sort(graph2));
		System.out.println(DFS.Strongly_Connected_Components(graph2));
		System.out.println(DFS.Strongly_Connected_Components(graph4));
		
		System.out.println(MST.MST_Kruskal(graph5).toString());
		System.out.println(MST.MST_Prim(graph5, 0).toString());
		
		//System.out.println(BFS.PrintPath(graph1, 1, 3));
		//System.out.println(DFS.parenthesis(graph1));
		
		//System.out.println("Matrix list:");
		//System.out.println(BFS.PrintPath(graph2, 1, 3));
		//System.out.println(DFS.parenthesis(graph2));
	}
	
	private static void fill(Graph graph) {
		graph.addEdge(0, 1);
		//graph.addEdge(0, 4);
		graph.addEdge(1, 5);
		graph.addEdge(1, 4);
		graph.addEdge(1, 2);
		graph.addEdge(2, 3);
		graph.addEdge(2, 6);
		graph.addEdge(3, 2);
		graph.addEdge(3, 7);
		graph.addEdge(4, 0);
		graph.addEdge(3, 5);
		graph.addEdge(5, 6);
		graph.addEdge(6, 5);
		graph.addEdge(6, 7);
		
	}
	
	private static int lq(char c) {
		return (c - 'q');
	}
	
	private static int la(char c) {
		return (c - 'a');
	}
	
	private static void fill2(Graph graph) {
		graph.addEdge(lq('q'), lq('s'));
		graph.addEdge(lq('q'), lq('w'));
		graph.addEdge(lq('q'), lq('t'));
		graph.addEdge(lq('r'), lq('y'));
		graph.addEdge(lq('r'), lq('u'));
		graph.addEdge(lq('s'), lq('v'));
		graph.addEdge(lq('t'), lq('x'));
		graph.addEdge(lq('t'), lq('y'));
		graph.addEdge(lq('u'), lq('y'));
		graph.addEdge(lq('v'), lq('w'));
		graph.addEdge(lq('w'), lq('s'));
		graph.addEdge(lq('x'), lq('z'));
		graph.addEdge(lq('y'), lq('q'));
		graph.addEdge(lq('z'), lq('x'));
		
	}
	
	private static void fill3(Graph graph) {
		graph.addEdge(la('a'), la('b'), 4);
		graph.addEdge(la('a'), la('h'), 8);
		graph.addEdge(la('b'), la('c'), 8);
		graph.addEdge(la('b'), la('h'), 11);
		graph.addEdge(la('c'), la('i'), 2);
		graph.addEdge(la('c'), la('f'), 4);
		graph.addEdge(la('c'), la('d'), 7);
		graph.addEdge(la('d'), la('f'), 14);
		graph.addEdge(la('d'), la('e'), 9);
		graph.addEdge(la('e'), la('f'), 10);
		graph.addEdge(la('f'), la('g'), 2);
		graph.addEdge(la('g'), la('i'), 6);
		graph.addEdge(la('g'), la('h'), 1);
		graph.addEdge(la('h'), la('i'), 7);
	}

}
